Joachim Breitner: Making dictionary passing explicit in Haskell
Haskell provides type classes to support polymorphism. A type class defines a few methods, which can then be implemented for a concrete type in the type class instance. This is a powerful system, but it also has it drawbacks. Most notably, each type can have at most one implementation of the type class. But sometimes you need to use a different implementation.
If, for example, you used the Binary class to store data on disk. Now you changed your data type and the binary instance, and you can not read the old data any more. One solution is to re-name your type using newtype and implement another type instance for that. Often, this is enough. But still, instances are not first-class-citizens. You can not pass them around or modify them, as you can pass around and modify data and functions.
Under the hood of the compiler, things look different. The ghc puts the methods of the instance in a dictionary and passes that implicitly to any functions having a (Class a) constraint. (Other implementations exist though) If one could make that behavior explicit, one could easily modify the instance before passing it to the function. But this is unfortunately not possible.
But it is possible to pass an explicit dictionary along the data. I use the Monoid class as an example, and define a representation of the dictionary to-be-passed, as well as the dictionary of the default instance:
data MonoidDict a = MonoidDict
ed_mempty :: a
, ed_mappend :: a -> a -> a
monoidDict :: Monoid a => MonoidDict a
monoidDict = MonoidDict mempty mappend
(For conciseness, I ignore the mconcat method.) My first idea was to pass this instance along with data: (MonoidDict a, a). But this would not work because there are methods, such as mempty, who need the dictionary without getting passed a value to use. Therefore, I need to put the dictionary both in the covariant and the contravariant position:
newtype WithMonoidDict a = WithMonoidDict (MonoidDict a -> (MonoidDict a, a))We need functions to clamp a dictionary to a value, and to extract it again:
wrapWithCustomMonoidDict :: MonoidDict a -> a -> WithMonoidDict a wrapWithCustomMonoidDict dict val = WithMonoidDict $ const (dict, val) extractFromCustomMonoidDict :: MonoidDict a -> WithMonoidDict a -> a extractFromCustomMonoidDict dict (WithMonoidDict f) = snd (f dict)Note that both expect the dictionary, so that it can be fed into WithMonoidDict from both sides . For convenience, we can define variants that use the standard instance:
wrapWithMonoidDict :: Monoid a => a -> WithMonoidDict a wrapWithMonoidDict = wrapWithCustomMonoidDict monoidDict extractFromMonoidDict :: Monoid a => WithMonoidDict a -> a extractFromMonoidDict = extractFromCustomMonoidDict monoidDictWe want to be able to pass the wrapped values as any other value with a Monoid instance, so we need to declare that:
instance Monoid (WithMonoidDict a) where mempty = WithMonoidDict (\d -> (d, ed_mempty d)) mappend (WithMonoidDict f1) (WithMonoidDict f2) = WithMonoidDict $ \d -> let (d1,v1) = f1 d (d2,v2) = f2 d in (d1, ed_mappend d1 v1 v2)Note that mappend has the choice between three dictionaries This is not a good sign, but let s hope that they are all the same. Does it work? Let s see:
listInstance :: MonoidDict [a] listInstance = monoidDict reverseInstance :: MonoidDict [a] reverseInstance = monoidDict ed_mappend = \l1 l2 -> l2 ++ l1 examples = do let l1 = [1,2,3] let l2 = [4,5,6] putStrLn $ "Example lists: " ++ show l1 ++ " " ++ show l2 putStrLn $ "l1 ++ l2: " ++ show (l1 ++ l2) putStrLn $ "l1 mappend l2: " ++ show (l1 mappend l2) putStrLn $ "Wrapped with default instance:" putStrLn $ "l1 mappend l2: " ++ show ( extractFromMonoidDict $ wrapWithMonoidDict l1 mappend wrapWithMonoidDict l2) putStrLn $ "Same with reversed monoid instance:" putStrLn $ "l1 mappend l2: " ++ show ( extractFromCustomMonoidDict reverseInstance $ wrapWithCustomMonoidDict reverseInstance l1 mappend wrapWithCustomMonoidDict reverseInstance l2)Running examples gives this output:
Example lists: [1,2,3] [4,5,6] l1 ++ l2: [1,2,3,4,5,6] l1 mappend l2: [1,2,3,4,5,6] Wrapped with default instance: l1 mappend l2: [1,2,3,4,5,6] Same with reversed monoid instance: l1 mappend l2: [4,5,6,1,2,3]Indeed it works. Unfortunately, this approach is not sufficient for all cases. It is perfectly valid to have a function with signature (Monoid a => Maybe a -> Maybe a), whose behavior depends on the instance of a, even when being passed Nothing and returning Nothing. Such a function woul<monoid a="a">d have a problem here, because the dictionary would not be passed to the function.
</monoid> I wonder if it would be possible to extend the Haskell language somehow to be able to properly pass an alternative dictionary to such functions. But given that not all compilers use dictionary passing, my hopes are low.
It takes a lot to prepare for a big trip if you want to really enjoy it. This time, we re going to Japan, and we bought some stuff to stay connected there.
First, there s the new camera: that s a Sony 230. We haven t made a photo trip to see all its capabilities yet, but it looks like an excellent toy so far. You ll see probably more photos on this blog in the future.
And there s the new laptop: a Packard-Bell Dot-M/A.
Theoretically it s called a netbook, but in practice it has everything a real laptop has. The reason I chose this model is that it features Radeon (X1270) graphics and a 64-bit processor, all in a 11,6" laptop which is one of the cheapest of all. Lots of power in one kilogram for a low price, although the drawback is more cells in the battery.
Getting the Dot-M/A to work under Debian
I first tried to install lenny on it, and while it worked nicely there are several problems with hardware support.
Arnt Karlsen reported 
#550000 sndfile-programs: ..trying to overwrite '/usr/share/man/man1/sndfile-cmp.1.gz', which is also in package libsndfile1 0:1.0.20-2
HP apparently decided my 2510p was cursed and replaced it with a 2530p which arrived earlier this week. A bit of playing later and it all seems pretty happy. Backlight control works fine, though you'll need hal-info git to get the hotkeys working out of the box. Sound needs alsa from 2.6.30 or for snd_hda_intel to be loaded with the "model=laptop" parameter. Suspend seems to work out of the box. Hotkeys and rfkill work with hp-wmi. The webcam is supported by the uvcvideo driver. The wwan modem needs qcserial from 2.6.30 and 
Since it took me more than one hour to figure out (and the documentation wasn't
too helpful), here's how to enumerate audio devices in GStreamer:
So I replaced my Latitude D410 with a shiny new Latitude E4300 (Intel Core 2 Duo SP9400 2.4 Ghz with 4 Gb RAM). Here are some notes about this laptop that might be interesting for others.
SSD disk
I now use an SSD drive for my main disk (Dell Ultra Performance SSD, it s the second generation of Samsung SSD) and I m satisfied with that choice, I can boot (an unmodified Debian desktop install) from the SSD in less than 30 seconds while the same system booting from a traditional hard-disk takes more than 45 seconds.
X server
The Intel GM45 graphic card is not auto-recognized by Xorg 7.3 (or rather by xserver-xorg-video-intel 2.3.2 which is in lenny) so you end up with the vesa driver by default. It s possible to force the usage of the intel driver by adding a Driver intel line in the device section of xorg.conf but I have opted to use Xorg 7.4 (available in experimental). With this version, I can successfully use the DVI output in the associated dock and I have working suspend/resume. It does create some interesting problems however since that version of the xserver relies on HAL to detect the keyboard layout and doesn t use the Keyboard section of xorg.conf. You have to create 
I have finally bought an EeePC 901, mainly to use for travelling.
Risto Suominen contacted me recently, after seeing 
Today was a good day — at least if I average all the things
happened today. And since 
